힙(Heap)

힙이란?

힙은 특별한 규칙이 있는 완전 이진 트리입니다.

• 최대 힙: 부모가 항상 자식보다 크거나 같습니다
• 최소 힙: 부모가 항상 자식보다 작거나 같습니다

최대 힙 예시:
       9
     /   \
    7     8
   / \   / \
  3   5 4   6
  
최소 힙 예시:
       1
     /   \
    3     2
   / \   / \
  7   5 6   4

왜 힙을 사용하나요?

가장 큰 값이나 가장 작은 값을 빠르게 찾고 싶을 때 사용합니다.

• 최대값/최소값 찾기: O(1)
• 삽입/삭제: O(log n)

힙 구현

배열로 구현하는 최소 힙

class MinHeap {
    constructor() {
        this.heap = [];
    }
    
    // 부모 인덱스 구하기
    getParentIndex(index) {
        return Math.floor((index - 1) / 2);
    }
    
    // 왼쪽 자식 인덱스
    getLeftChildIndex(index) {
        return 2 * index + 1;
    }
    
    // 오른쪽 자식 인덱스
    getRightChildIndex(index) {
        return 2 * index + 2;
    }
    
    // 두 값 바꾸기
    swap(index1, index2) {
        [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
    }
    
    // 삽입
    insert(value) {
        this.heap.push(value);
        this.heapifyUp();
    }
    
    // 위로 올리기 (삽입 후)
    heapifyUp() {
        let index = this.heap.length - 1;
        
        while (index > 0) {
            const parentIndex = this.getParentIndex(index);
            
            if (this.heap[parentIndex] <= this.heap[index]) {
                break;
            }
            
            this.swap(parentIndex, index);
            index = parentIndex;
        }
    }
    
    // 최소값 제거
    extractMin() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();
        
        const min = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.heapifyDown();
        
        return min;
    }
    
    // 아래로 내리기 (제거 후)
    heapifyDown() {
        let index = 0;
        
        while (this.getLeftChildIndex(index) < this.heap.length) {
            let smallerChildIndex = this.getLeftChildIndex(index);
            const rightChildIndex = this.getRightChildIndex(index);
            
            if (rightChildIndex < this.heap.length && 
                this.heap[rightChildIndex] < this.heap[smallerChildIndex]) {
                smallerChildIndex = rightChildIndex;
            }
            
            if (this.heap[index] <= this.heap[smallerChildIndex]) {
                break;
            }
            
            this.swap(index, smallerChildIndex);
            index = smallerChildIndex;
        }
    }
    
    // 최소값 확인 (제거하지 않음)
    peek() {
        return this.heap.length === 0 ? null : this.heap[0];
    }
    
    // 크기
    size() {
        return this.heap.length;
    }
    
    // 비어있는지 확인
    isEmpty() {
        return this.heap.length === 0;
    }
}

최대 힙 구현

class MaxHeap {
    constructor() {
        this.heap = [];
    }
    
    getParentIndex(index) {
        return Math.floor((index - 1) / 2);
    }
    
    getLeftChildIndex(index) {
        return 2 * index + 1;
    }
    
    getRightChildIndex(index) {
        return 2 * index + 2;
    }
    
    swap(index1, index2) {
        [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
    }
    
    insert(value) {
        this.heap.push(value);
        this.heapifyUp();
    }
    
    heapifyUp() {
        let index = this.heap.length - 1;
        
        while (index > 0) {
            const parentIndex = this.getParentIndex(index);
            
            if (this.heap[parentIndex] >= this.heap[index]) {
                break;
            }
            
            this.swap(parentIndex, index);
            index = parentIndex;
        }
    }
    
    extractMax() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();
        
        const max = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.heapifyDown();
        
        return max;
    }
    
    heapifyDown() {
        let index = 0;
        
        while (this.getLeftChildIndex(index) < this.heap.length) {
            let largerChildIndex = this.getLeftChildIndex(index);
            const rightChildIndex = this.getRightChildIndex(index);
            
            if (rightChildIndex < this.heap.length && 
                this.heap[rightChildIndex] > this.heap[largerChildIndex]) {
                largerChildIndex = rightChildIndex;
            }
            
            if (this.heap[index] >= this.heap[largerChildIndex]) {
                break;
            }
            
            this.swap(index, largerChildIndex);
            index = largerChildIndex;
        }
    }
    
    peek() {
        return this.heap.length === 0 ? null : this.heap[0];
    }
    
    size() {
        return this.heap.length;
    }
    
    isEmpty() {
        return this.heap.length === 0;
    }
}

다른 방법들과 성능 비교

최대값 찾기 비교

function compareMaxFinding() {
    const data = Array.from({length: 100000}, () => Math.floor(Math.random() * 1000000));
    
    // 1. 배열에서 Math.max 사용
    let start = performance.now();
    for (let i = 0; i < 1000; i++) {
        Math.max(...data);
    }
    let end = performance.now();
    const mathMaxTime = end - start;
    
    // 2. 배열 순회로 최대값 찾기
    start = performance.now();
    for (let i = 0; i < 1000; i++) {
        let max = data[0];
        for (let j = 1; j < data.length; j++) {
            if (data[j] > max) max = data[j];
        }
    }
    end = performance.now();
    const loopTime = end - start;
    
    // 3. 최대 힙 사용
    const maxHeap = new MaxHeap();
    data.forEach(value => maxHeap.insert(value));
    
    start = performance.now();
    for (let i = 0; i < 1000; i++) {
        maxHeap.peek(); // 최대값 확인만
    }
    end = performance.now();
    const heapTime = end - start;
    
    console.log(`Math.max: ${mathMaxTime.toFixed(2)}ms`);
    console.log(`반복문: ${loopTime.toFixed(2)}ms`);
    console.log(`힙: ${heapTime.toFixed(2)}ms`);
}

힙은 최대값 찾기가 O(1)이므로 반복적으로 최대값을 찾을 때 가장 빠릅니다

정렬 비교 (힙 정렬 vs 다른 정렬들)

function compareSort() {
    const size = 10000;
    
    // 테스트 데이터 생성
    function generateRandomArray() {
        return Array.from({length: size}, () => Math.floor(Math.random() * size));
    }
    
    // 힙 정렬
    function heapSort(arr) {
        const heap = new MaxHeap();
        arr.forEach(value => heap.insert(value));
        
        const result = [];
        while (!heap.isEmpty()) {
            result.unshift(heap.extractMax());
        }
        return result;
    }
    
    // 성능 테스트
    let data = generateRandomArray();
    let start = performance.now();
    heapSort([...data]);
    let end = performance.now();
    const heapSortTime = end - start;
    
    data = generateRandomArray();
    start = performance.now();
    [...data].sort((a, b) => a - b);
    end = performance.now();
    const quickSortTime = end - start;
    
    data = generateRandomArray();
    start = performance.now();
    bubbleSort([...data]);
    end = performance.now();
    const bubbleSortTime = end - start;
    
    console.log(`힙 정렬: ${heapSortTime.toFixed(2)}ms`);
    console.log(`자바스크립트 내장 정렬: ${quickSortTime.toFixed(2)}ms`);
    console.log(`버블 정렬: ${bubbleSortTime.toFixed(2)}ms`);
}

function bubbleSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;
}

JavaScript 내장 정렬이 가장 빠르고, 힙 정렬은 중간, 버블 정렬이 가장 느립니다

우선순위 큐로 활용

힙은 우선순위 큐를 만들 때 가장 많이 사용됩니다.

class PriorityQueue {
    constructor(isMaxPriority = false) {
        this.heap = isMaxPriority ? new MaxHeap() : new MinHeap();
    }
    
    enqueue(value, priority) {
        this.heap.insert({value, priority});
    }
    
    dequeue() {
        const item = this.heap.extractMin() || this.heap.extractMax();
        return item ? item.value : null;
    }
    
    peek() {
        const item = this.heap.peek();
        return item ? item.value : null;
    }
    
    isEmpty() {
        return this.heap.isEmpty();
    }
    
    size() {
        return this.heap.size();
    }
}

// 우선순위가 낮은 숫자일수록 먼저 처리되는 큐
class MinPriorityQueue extends MinHeap {
    insert(value, priority) {
        super.insert({value, priority});
    }
    
    heapifyUp() {
        let index = this.heap.length - 1;
        
        while (index > 0) {
            const parentIndex = this.getParentIndex(index);
            
            if (this.heap[parentIndex].priority <= this.heap[index].priority) {
                break;
            }
            
            this.swap(parentIndex, index);
            index = parentIndex;
        }
    }
    
    heapifyDown() {
        let index = 0;
        
        while (this.getLeftChildIndex(index) < this.heap.length) {
            let smallerChildIndex = this.getLeftChildIndex(index);
            const rightChildIndex = this.getRightChildIndex(index);
            
            if (rightChildIndex < this.heap.length && 
                this.heap[rightChildIndex].priority < this.heap[smallerChildIndex].priority) {
                smallerChildIndex = rightChildIndex;
            }
            
            if (this.heap[index].priority <= this.heap[smallerChildIndex].priority) {
                break;
            }
            
            this.swap(index, smallerChildIndex);
            index = smallerChildIndex;
        }
    }
    
    extractMin() {
        const item = super.extractMin();
        return item ? item.value : null;
    }
    
    peek() {
        const item = super.peek();
        return item ? item.value : null;
    }
}

실제 문제 예시

K번째로 큰 수 찾기

function findKthLargest(nums, k) {
    const minHeap = new MinHeap();
    
    // k개만 유지하는 최소 힙
    for (let num of nums) {
        minHeap.insert(num);
        if (minHeap.size() > k) {
            minHeap.extractMin();
        }
    }
    
    return minHeap.peek();
}

console.log(findKthLargest([3,2,1,5,6,4], 2)); // 5 (2번째로 큰 수)
console.log(findKthLargest([3,2,3,1,2,4,5,5,6], 4)); // 4 (4번째로 큰 수)

작업 스케줄링

function scheduleJobs(jobs) {
    // 우선순위가 높은 작업부터 처리
    const priorityQueue = new MinPriorityQueue();
    
    jobs.forEach(job => {
        priorityQueue.insert(job.name, job.priority);
    });
    
    const schedule = [];
    while (!priorityQueue.isEmpty()) {
        schedule.push(priorityQueue.extractMin());
    }
    
    return schedule;
}

const jobs = [
    {name: "이메일 확인", priority: 3},
    {name: "긴급 회의", priority: 1},
    {name: "점심 식사", priority: 5},
    {name: "보고서 작성", priority: 2},
    {name: "코드 리뷰", priority: 2}
];

console.log(scheduleJobs(jobs));
// ["긴급 회의", "보고서 작성", "코드 리뷰", "이메일 확인", "점심 식사"]

언제 사용하나요?

• 가장 큰/작은 값을 자주 찾아야 할 때
• 우선순위 큐가 필요할 때
• 데이터를 부분적으로 정렬하고 싶을 때
• 메모리를 효율적으로 사용하면서 빠른 접근이 필요할 때

힙은 완전 이진 트리 구조를 배열로 구현하므로 메모리를 효율적으로 사용하면서도 빠른 성능을 제공합니다.